Search Results

Documents authored by Oppenheim, Izhar

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.5
High Dimensional Expansion Implies Amplified Local Testability

Authors: Tali Kaufman and Izhar Oppenheim

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
In this work, we define a notion of local testability of codes that is strictly stronger than the basic one (studied e.g., by recent works on high rate LTCs), and we term it amplified local testability. Amplified local testability is a notion close to the result of optimal testing for Reed-Muller codes achieved by Bhattacharyya et al. We present a scheme to get amplified locally testable codes from high dimensional expanders. We show that single orbit Affine invariant codes, and in particular Reed-Muller codes, can be described via our scheme, and hence are amplified locally testable. This gives the strongest currently known testability result of single orbit affine invariant codes, strengthening the celebrated result of Kaufman and Sudan.
Cite as

Tali Kaufman and Izhar Oppenheim. High Dimensional Expansion Implies Amplified Local Testability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.5,
  author =	{Kaufman, Tali and Oppenheim, Izhar},
  title =	{{High Dimensional Expansion Implies Amplified Local Testability}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.5},
  URN =		{urn:nbn:de:0030-drops-171276},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.5},
  annote =	{Keywords: Locally testable codes, High dimensional expanders, Amplified testing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.84
Coboundary and Cosystolic Expansion from Strong Symmetry

Authors: Tali Kaufman and Izhar Oppenheim

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not have high dimensional edge-expansion. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, prior to this work, the only known bounded degree cosystolic expanders were derived from the theory of buildings that is far from being elementary. In this work we study high dimensional complexes which are strongly symmetric. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove coboundary and cosystolic expansion. It was an open question whether the recent elementary construction of bounded degree spectral high dimensional expanders based on coset complexes give rise to bounded degree cosystolic expanders. In this work we answer this question affirmatively. We show that these complexes give rise to bounded degree cosystolic expanders in dimension two, and that their links are (two-dimensional) coboundary expanders. We do so by exploiting the strong symmetry properties of the links of these complexes using a new machinery developed in this work. Previous works have shown a way to bound the co-boundary expansion using strong symmetry in the special situation of "building like" complexes. Our new machinery shows how to get coboundary expansion for general strongly symmetric coset complexes, which are not necessarily "building like", via studying the (Dehn function of the) presentation of the symmetry group of these complexes.
Cite as

Tali Kaufman and Izhar Oppenheim. Coboundary and Cosystolic Expansion from Strong Symmetry. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ICALP.2021.84,
  author =	{Kaufman, Tali and Oppenheim, Izhar},
  title =	{{Coboundary and Cosystolic Expansion from Strong Symmetry}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.84},
  URN =		{urn:nbn:de:0030-drops-141539},
  doi =		{10.4230/LIPIcs.ICALP.2021.84},
  annote =	{Keywords: High dimensional expanders, Cosystolic expansion, Coboundary expansion}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.47
High Order Random Walks: Beyond Spectral Gap

Authors: Tali Kaufman and Izhar Oppenheim

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We study high order random walks on high dimensional expanders on simplicial complexes (i.e., hypergraphs). These walks walk from a k-face (i.e., a k-hyperedge) to a k-face if they are both contained in a k+1-face (i.e, a k+1 hyperedge). This naturally generalizes the random walks on graphs that walk from a vertex (0-face) to a vertex if they are both contained in an edge (1-face). Recent works have studied the spectrum of high order walks operators and deduced fast mixing. However, the spectral gap of high order walks operators is inherently small, due to natural obstructions (called coboundaries) that do not happen for walks on expander graphs. In this work we go beyond spectral gap, and relate the expansion of a function on k-faces (called k-cochain, for k=0, this is a function on vertices) to its structure. We show a Decomposition Theorem: For every k-cochain defined on high dimensional expander, there exists a decomposition of the cochain into i-cochains such that the square norm of the k-cochain is a sum of the square norms of the i-chains and such that the more weight the k-cochain has on higher levels of the decomposition the better is its expansion, or equivalently, the better is its shrinkage by the high order random walk operator. The following corollaries are implied by the Decomposition Theorem: - We characterize highly expanding k-cochains as those whose mass is concentrated on the highest levels of the decomposition that we construct. For example, a function on edges (i.e. a 1-cochain) which is locally thin (i.e. it contains few edges through every vertex) is highly expanding, while a function on edges that contains all edges through a single vertex is not highly expanding. - We get optimal mixing for high order random walks on Ramanujan complexes. Ramanujan complexes are recently discovered bounded degree high dimensional expanders. The optimality in their mixing that we prove here, enable us to get from them more efficient Two-Layer-Samplers than those presented by the previous work of Dinur and Kaufman.
Cite as

Tali Kaufman and Izhar Oppenheim. High Order Random Walks: Beyond Spectral Gap. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.APPROX-RANDOM.2018.47,
  author =	{Kaufman, Tali and Oppenheim, Izhar},
  title =	{{High Order Random Walks: Beyond Spectral Gap}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.47},
  URN =		{urn:nbn:de:0030-drops-94516},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.47},
  annote =	{Keywords: High Dimensional Expanders, Simplicial Complexes, Random Walk}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact